Practice | GeeksforGeeks | A computer science portal for geeks
▲
LIVE   BATCHES
 Back To Course
Quiz

This track of the course covers the topic "BST".

In details, this track will cover:

  • Basics: Introduction to BSTs and properties.
  • Operations: Creation, Insertion, Deletion and other operations like LCA.
  • Implementation: How to implement BSTs.
  • Balancing: How to balance a BST.

Objective: The objective of this track is to familiarize the learners with BSTs.

Track Content:

  • 4 Video Lecture on BST.
  • Theoretical Articles.
  • Programming practice problems.
  • 10 Quiz questions for practice.

Assessment: All Tracks in every week are associated with weekly contests.

We have combined Classroom and Theory tab and created a new Learn tab for easy access. You can access Classroom and Theory from the left panel.
Classroom Theory

  Binary Search Tree(Background) 


In this video we compare time complexity of different operations on different datastructures and deduce the importance of Binary Search Tree.

  Binary Search Tree(Introduction) 


In this video we take a brief introduction about Binary Search Trees.Also we briefly discuss about different operations on Binary Search Trees.

  Search in BST (Introduction) 


In this video we discuss about search operation in Binary Serach Tree. The basic idea is that we end up with a leaf note if the key is not present in the BST.

  Search in BST C++ 


In this video we discuss two methods (recursive and iterative) to implement a function in C++ that takes root and key as parameters and return True if the key is present in the BST and returns False if the key is not present in BST.
Codes:

  Search in BST Java 


In this video we discuss two methods (recursive and iterative) to implement a function in Java that takes root and key as parameters and return True if the key is present in the BST and returns False if the key is not present in BST.
Codes:

  Insert in BST 


In this video we learn how to insert a node in a BST, the basic idea is that we first search for the key and if the key is not present in the BST then we insert the key with the leaf node. Else if the key is already present in the BST then we do nothing.

  Insert in BST C++ 


In this video we discuss two methods(recursive and iterative) to insert to a node in a Binary Search Tree in C++.
Codes:

  Insert in BST Java 


In this video we discuss two methods(recursive and iterative) to insert a node in a BST in Java.
Codes:

  Deletion in BST 


In this video we discuss how to delete a node from a Binary Search There are three posibilities:
1.Node to be deleted is a leaf node.
2.Node to be deleted has only one child.
3.Node to be deleted has two children.
we also learn, inorder successor is the closest higher value and inorder predecessor is the closest lower value.

  BST deletion in C++ 


BST Deletion in Cpp
Code:

  BST Deletion in Java 


BST Deletion in Java
Code:

  Floor in BST 


This video discusses the concept of Floor in Binary Search Tree along with the discussion on time complexity.

  Floor in BST in CPP 


This video deals with the concept of the floor in Binary Search Tree and its implementation in C++.
Code:

  Floor in BST Java 


This video deals with the concept of the floor in Binary Search Tree and its implementation in Java.
Code:

  Ceil in BST 


This video deals with the concept and working of the ceiling of a key in Binary Search Tree.
Codes:

  Self Balancing BST 


This video discusses the working of a Self Balancing Binary Search Tree.

  AVL Tree 


This video discusses the AVL tree. This is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

  Red Black Tree 


This video discusses the Red-Black Tree. This is a self-balancing Binary Search Tree (BST) where every node follows the following rules:

  1. Every node has a color either red or black.
  2. The root of tree is always black.
  3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
  4. Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

  Applications of BST 


This video discusses the various applications of a binary search tree.

  Set in C++ STL 


This video introduces us to Set in the C++ STL class. It also shows the implementation of the set through examples and explains few functions associated with the Set STL class in C++.
Codes:

  Map in C++ STL 


This video introduces us to Map in the C++ STL class. It also shows the implementation of the set through examples and explains few functions associated with the Map STL class in C++.
Codes:

  TreeSet In java 


This video explains Tree Set In Java and the various operations involved with it.

Codes:

  TreeMap in Java 


This video explains TreeMap In Java and the various operations involved with it.

Codes:

  Ceiling on left side in an array 


This video discusses the problem of accepting an array and for every element of the array, one needs to find the Ceiling on Left Side.
Codes:

  Find Kth Smallest in BST 


This video discusses the problem of finding the Kth Smallest Binary Search Tree.
Codes:

  Check for BST 


This video discusses the problem of checking whether a binary tree is a binary search tree or not.
Codes:

  Fix BST with Two Nodes Swapped 


Given a binary search tree with two swapped nodes, the task is to fix the binary search tree by swapping them back.
Codes:

  Pair Sum with given BST 


The problem discusses finding the pair of the sum in given Binary Search Tree.
Codes:

  Vertical Sum in a Binary Tree 


Given a binary tree, we need to find sum of nodes in all vertical lines starting from leftmost line to rightmost.
Codes:

  Vertical Traversal of Binary Tree 


Given a binary tree, we need to print nodes in all vertical lines starting from leftmost line to rightmost.
Codes:

  Top View of Binary Tree 


A Vertical Traversal based approach is discussed in this video
Codes:

  Bottom View of Binary Tree 


A solution using Vertical Traversal is discussed in the video
Codes:

  Introduction to Binary Search Trees 

Binary Search Tree is a node-based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys lesser than or equal to the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • The left and right subtree each must also be a binary search tree.
    There must be no duplicate nodes.

Sample Binary Search Tree:
200px-Binary_search_tree.svg

The above properties of Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done fast in comparison to normal Binary Trees. If there is no ordering, then we may have to compare every key to search a given key.

Searching a Key

Using the property of Binary Search Tree, we can search for an element in O(h) time complexity where h is the height of the given BST.

To search a given key in Binary Search Tree, first compare it with root, if the key is present at root, return root. If the key is greater than the root's key, we recur for the right subtree of the root node. Otherwise, we recur for the left subtree.

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Illustration to search a key 6 in the below BST:
  1. Start from root.
  2. Compare the key element with root, if less than root, then recur for left subtree, else recur for right subtree.
  3. If element to search is found anywhere, return true, else return false.

bstsearch

Step 1: Compare 6 with 8.
        Since 6 is less than 8, 
        move to left subtree.
Step 2: Compare 6 with 3.
        Since 6 is greater than 3, 
        move to its right subtree.
Step 3: Comapre 6 with 6.
        Node Found.

Insertion of a Key

Inserting a new node in the Binary Search Tree is always done at the leaf nodes to maintain the order of nodes in the Tree. The idea is to start searching the given node to be inserted from the root node till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

For Example:
         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40


Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output: 
20 30 40 50 60 70 80

Illustration to insert 2 in the below tree:
  1. Start from root.
  2. Compare the element to be inserted with root, if it is less than root, then recur for left-subtree, else recur for right-subtree.
  3. After reaching end,just insert that node at left(if less than current leaf node) else right.
bstsearch

Element to be inserted: 2

Step 1: Compare 2 with 8.
        Since 2 is less than 8, 
        move to left subtree.
Step 2: Compare 2 with 3.
        Since 2 is less than 3, 
        move to its left subtree.
Step 3: Comapre 2 with 1.
        Since 2 is greater than 1 and also 1 is a leaf node.
        Insert 2 as its right child of node 1.

Time Complexity: The worst case time complexity of search and insert operations is O(h) where h is height of Binary Search Tree. In the worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).

  Deletion in a Binary Search Tree 

We have discussed the Search and Insert operations in BST in the previous post. In this post, delete operation is discussed.

That is, given a Binary Search Tree and a node to be deleted. The task is to search that node in the given BST and delete it from the BST if it is present.

When we delete a node, three cases may arise:
  1. Node to be deleted is leaf: Simply remove from the tree.
  2. Node to be deleted has only one child: Copy the child to the node and delete the child.

  3. Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.


Note: The inorder successor can be obtained by finding the minimum value in the right child of the node.
Below is the implementation of the above three cases:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output: 
Inorder traversal of the given tree
20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80

Illustration: bst-delete

bst-delete2

  Finding LCA in Binary Search Tree 

We have already seen the definition of LCA and finding LCA of any two nodes in a Binary Tree in the previous post.

Let's look at the process of finding LCA in a Binary Search Tree.

Problem: Given values of two values n1 and n2 in a Binary Search Tree, find the Lowest Common Ancestor (LCA). For Simplicity, you may assume that both the values exist in the tree.

Consider the below BST:
BST_LCA
In the above BST:
LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.

Finding LCA

Since Binary Search Tree is also a Binary Tree, we can apply the same process of finding LCA of two nodes in BST as that of binary trees. But finding LCA in a Binary Tree takes O(N) time complexity.

However, we can solve this problem using BST properties. We can recursively traverse the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 <= n <= n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST, if node's value is greater than both n1 and n2 then our LCA lies in the left subtree of the node, if it's is smaller than both n1 and n2, then LCA lies on the right subtree. Otherwise root is LCA (assuming that both n1 and n2 are present in BST).

Below is the implementation of this approach:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output: 
LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

The time complexity of the above solution is O(h) where h is the height of the tree. Also, the above solution requires O(h) extra space in function call stack for recursive function calls. We can avoid extra space using iterative solution.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Introduction to AVL Tree 

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

An Example Tree that is an AVL Tree:

The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1.

An Example Tree that is NOT an AVL Tree:

The above tree is not AVL because differences between heights of left and right subtrees for 8 and 18 is greater than 1.

Why AVL Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree.

Insertion

To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
  1. Left Rotation
  2. Right Rotation

T1, T2 and T3 are subtrees of the tree 
rooted with y (on the left side) or x (on 
the right side)        

Keys in both of the above trees follow the 
following order: 
 keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)

So BST property is not violated anywhere.


Steps to follow for insertion: Let the newly inserted node be w.
  1. Perform standard BST insert for w.
  2. Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
  3. Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that need to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
    • y is left child of z and x is left child of y (Left Left Case)
    • y is left child of z and x is right child of y (Left Right Case)
    • y is right child of z and x is right child of y (Right Right Case)
    • y is right child of z and x is left child of y (Right Left Case)

Following are the operations to be performed in above mentioned 4 cases. In all of the cases, we only need to re-balance the subtree rooted with z and the complete tree becomes balanced as the height of subtree (After appropriate rotations) rooted with z becomes same as it was before insertion. (See this video lecture for proof)

a) Left Left Case 
T1, T2, T3 and T4 are subtrees.


b) Left Right Case



c) Right Right Case



d) Right Left Case


Insertion Examples: avlinsert1
avlinsert2-jpg
avlinsert3
avlinsert4
avlinsert5
Time Complexity: The rotation operations (left and right rotate) take constant time as only a few pointers are being changed there. Updating the height and getting the balance factor also takes constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where h is the height of the tree. Since the AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).
Inorder traversal of a BST
Submissions: 2756   Accuracy:

82.57%

  Difficulty: Easy   Marks: 2
Levelorder traversal of a BST
Submissions: 2496   Accuracy:

79.54%

  Difficulty: Easy   Marks: 2
Insert a node in a BST

Asked In: Accolite Amazon Microsoft Paytm Samsung

Submissions: 50159   Accuracy:

32.7%

  Difficulty: Easy   Marks: 2
Search a node in BST

Asked In: Linkedin

Submissions: 21187   Accuracy:

55.04%

  Difficulty: Basic   Marks: 1
Minimum element in BST

Asked In: Microsoft

Submissions: 39508   Accuracy:

62.66%

  Difficulty: Basic   Marks: 1
Find Common Nodes in two BSTs

Asked In: Amazon

Submissions: 15024   Accuracy:

49.82%

  Difficulty: Easy   Marks: 2
Delete a node from BST

Asked In: Accolite Adobe Amazon Qualcomm Samsung

Submissions: 41951   Accuracy:

34.76%

  Difficulty: Medium   Marks: 4
Lowest Common Ancestor in a BST

Asked In: Accolite Amazon Flipkart MAQ Software Microsoft Samsung Synopsys

Submissions: 59136   Accuracy:

50.22%

  Difficulty: Easy   Marks: 2
Print BST elements in given range

Asked In: Amazon Flipkart Microsoft

Submissions: 27896   Accuracy:

49.48%

  Difficulty: Easy   Marks: 2
Pair Sum in BST

Asked In: VMWare

Submissions: 3967   Accuracy:

55.48%

  Difficulty: Medium   Marks: 4
Smaller on Right
Submissions: 2923   Accuracy:

35.08%

  Difficulty: Medium   Marks: 4
Floor in BST
Submissions: 5950   Accuracy:

37.74%

  Difficulty: Medium   Marks: 4
Ceil in BST

Asked In: Samsung

Submissions: 5068   Accuracy:

57.42%

  Difficulty: Medium   Marks: 4
Vertical Traversal of Binary Tree

Asked In: Accolite Amazon BrowserStack Dell Flipkart Grofers MakeMyTrip Netskope Walmart Microsoft

Submissions: 78813   Accuracy:

32.45%

  Difficulty: Medium   Marks: 4
Top View of Binary Tree

Asked In: Amazon Ola Cabs Paytm Samsung Walmart

Submissions: 60478   Accuracy:

32.3%

  Difficulty: Medium   Marks: 4
Bottom View of Binary Tree

Asked In: Accolite Amazon CouponDunia Flipkart OYO Rooms Paytm Walmart

Submissions: 61996   Accuracy:

45.32%

  Difficulty: Medium   Marks: 4
Find the Closest Element in BST

Asked In: Amazon MAQ Software

Submissions: 22734   Accuracy:

49.94%

  Difficulty: Medium   Marks: 4
Convert Level Order Traversal to BST
Submissions: 10926   Accuracy:

54.25%

  Difficulty: Medium   Marks: 4
Count BST nodes that lie in a given range

Asked In: D-E-Shaw Google

Submissions: 36921   Accuracy:

50.5%

  Difficulty: Medium   Marks: 4
Question 1 [1 Marks]
What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
A
O(n) for all
B
O(Logn) for all
C
O(Logn) for search and insert, and O(n) for delete
D
O(Logn) for search, and O(n) for insert and delete
Explanation

DSASP-W6 LIVE

Binary Search Tree

Contest Max Score: 350

Duration: 2 Hrs 0 Mins

If you are facing any issue on this page. Please let us know.